﻿//T14 找出所有子集的异或总和再求和
//class Solution {
//public:
//    int path = 0;
//    int sum = 0;
//    int subsetXORSum(vector<int>& nums) {
//        dfs(nums, 0);
//        return sum;
//    }
//    void dfs(vector<int>& nums, int pos)
//    {
//        for (int i = pos; i < nums.size(); i++)
//        {
//            path ^= nums[i];
//            dfs(nums, i + 1);
//            path ^= nums[i];
//        }
//        sum += path;
//    }
//};

//T15 全排列二
//class Solution {
//public:
//    vector<vector<int>> ret;
//    vector<int> path;
//    bool check[9];
//    vector<vector<int>> permuteUnique(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        dfs(nums);
//        return ret;
//    }
//    void dfs(vector<int>& nums) {
//        if (nums.size() == path.size()) {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = 0; i < nums.size(); i++) {
//            if (check[i] == false &&    //合法
//                (i == 0 || nums[i - 1] != nums[i] || check[i - 1] == true))
//            {
//                path.push_back(nums[i]);
//                check[i] = true;
//                dfs(nums);
//                path.pop_back();
//                check[i] = false;
//            }
//        }
//    }
//};

//T16 电话号码的字母组合
//class Solution {
//    string hash[10] = { "",    "",    "abc",  "def", "ghi",
//                       "jkl", "mno", "pqrs", "tuv", "wxyz" };
//public:
//    vector<string> ret;
//    string path;
//    vector<string> letterCombinations(string digits) {
//        if (digits.empty())
//            return ret;
//        dfs(digits, 0);
//        return ret;
//    }
//    void dfs(string digits, int pos) {
//        if (pos == digits.size()) {
//            ret.push_back(path);
//            return;
//        }
//        string tmp = hash[digits[pos] - '0'];
//        for (int i = 0; i < tmp.size(); i++) {
//            path += tmp[i];
//            dfs(digits, pos + 1);
//            path.pop_back();
//        }
//    }
//};

//T17 括号生成
//class Solution {
//public:
//    vector<string> ret;
//    string path;
//    vector<string> generateParenthesis(int n) {
//        int left = n, right = n;
//        dfs(left, right);
//        return ret;
//    }
//    void dfs(int left, int right) {
//        if (left == 0 && right == 0) {
//            ret.push_back(path);
//            return;
//        }
//        if (left != 0) {
//            path.push_back('(');
//            dfs(left - 1, right);
//            path.pop_back();
//        }
//        if (left < right) {
//            path.push_back(')');
//            dfs(left, right - 1);
//            path.pop_back();
//        }
//    }
//};

//T18 组合	
//class Solution {
//    vector<vector<int>> ret;
//    vector<int> path;
//    int tn, tk;
//public:
//    vector<vector<int>> combine(int n, int k) {
//        tn = n;
//        tk = k;
//        dfs(1);
//        return ret;
//    }
//    void dfs(int pos) {
//        if (path.size() == tk) {
//            ret.push_back(path);
//            return;
//        }
//        for (int i = pos; i <= tn; i++) {
//            path.push_back(i);
//            dfs(i + 1);
//            path.pop_back();
//        }
//    }
//};

//T19 目标和
//class Solution {
//public:
//    int ret = 0;
//    int target_ = 0;
//    int findTargetSumWays(vector<int>& nums, int target) {
//        target_ = target;
//        dfs(nums, 0, 0);
//        return ret;
//    }
//    void dfs(vector<int>& nums, int pos, int sum)
//    {
//        if (pos == nums.size() && sum == target_)
//        {
//            ret++;
//            return;
//        }
//        if (pos == nums.size())
//            return;
//        dfs(nums, pos + 1, sum + nums[pos]);
//        dfs(nums, pos + 1, sum - nums[pos]);
//    }
//};

//T20 组合总数
//class Solution {
//public:
//    vector<vector<int>> ret;
//    vector<int> path;
//    int target_;
//    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//        target_ = target;
//        dfs(candidates, 0, 0);
//        return ret;
//    }
//    void dfs(vector<int>& n, int pos, int sum)
//    {
//        if (sum == target_)
//        {
//            ret.push_back(path);
//            return;
//        }
//        if (sum > target_ || pos == n.size())
//            return;
//        for (int i = pos; i < n.size(); i++)
//        {
//            path.push_back(n[i]);
//            dfs(n, i, sum + n[i]);
//            path.pop_back();
//        }
//    }
//};

//T21 字符大小写全排列
//class Solution {
//public:
//    vector<string> ret;
//    string path;
//    vector<string> letterCasePermutation(string s) {
//        dfs(s, 0);
//        return ret;
//    }
//    void dfs(string& s, int pos) {
//        if (pos == s.size()) {
//            ret.push_back(path);
//            return;
//        }
//        if (s[pos] >= '0' && s[pos] <= '9') {
//            path.push_back(s[pos]);
//            dfs(s, pos + 1);
//            path.pop_back();
//        }
//        else {
//            char ch = s[pos];
//            path.push_back(toupper(ch));
//            dfs(s, pos + 1);
//            path.pop_back();
//
//            path.push_back(tolower(ch));
//            dfs(s, pos + 1);
//            path.pop_back();
//        }
//    }
//};

//T22 优美的序列
//class Solution {
//    bool check[16];
//    int ret = 0;
//public:
//    int countArrangement(int n) {
//        dfs(1, n);
//        return ret;
//    }
//    void dfs(int pos, int n) {
//        if (pos == n + 1) {
//            ret++;
//            return;
//        }
//        for (int i = 1; i <= n; i++) {
//            if (!check[i] && (pos % i == 0 || i % pos == 0)) {
//                check[i] = true;
//                dfs(pos + 1, n);
//                check[i] = false;
//            }
//        }
//    }
//};

//T23 N皇后
//class Solution {
//    vector<vector<string>> ret;
//    vector<string> v;
//    int n;
//
//    bool col[9];
//    bool digL[18];
//    bool digR[18];
//public:
//    vector<vector<string>> solveNQueens(int _n) {
//        n = _n;
//        dfs(0);
//        return ret;
//    }
//    void dfs(int pos) {
//        if (pos == n) {
//            ret.push_back(v);
//            return;
//        }
//        for (int i = 0; i < n; i++) {
//            if (!col[i] && !digL[pos + i] && !digR[pos - i + n]) {
//                string s(n, '.');
//                s[i] = 'Q';
//                col[i] = true;
//                digL[pos + i] = true;
//                digR[pos - i + n] = true;
//                v.push_back(s);
//                dfs(pos + 1);
//                col[i] = false;
//                digL[pos + i] = false;
//                digR[pos - i + n] = false;
//                v.pop_back();
//            }
//        }
//    }
//};

//T24 有效的数独
//class Solution {
//    bool row[9][10];
//    bool col[9][10];
//    bool grid[3][3][10];
//public:
//    bool isValidSudoku(vector<vector<char>>& board) {
//        for (int i = 0; i < 9; i++) {
//            for (int j = 0; j < 9; j++) {
//                if (board[i][j] != '.') {
//                    int num = board[i][j] - '0';
//                    if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num])
//                        return false;
//                    else
//                        row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
//                }
//            }
//        }
//        return true;
//    }
//};

//T25 解数独
//class Solution {
//    bool row[9][10];
//    bool col[9][10];
//    bool grid[3][3][10];
//
//public:
//    void solveSudoku(vector<vector<char>>& board) {
//        for (int i = 0; i < 9; i++)
//            for (int j = 0; j < 9; j++)
//                if (board[i][j] != '.') {
//                    int num = board[i][j] - '0';
//                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
//                }
//        dfs(board);
//    }
//    bool dfs(vector<vector<char>>& board) {
//        int i, j;
//        for (i = 0; i < 9; i++)
//            for (j = 0; j < 9; j++) {
//                if (board[i][j] == '.') {
//                    for (int n = 1; n < 10; n++)
//                    {
//                        if (!row[i][n] && !col[j][n] && !grid[i / 3][j / 3][n])
//                        {
//                            board[i][j] = (char)(n + '0');
//                            row[i][n] = col[j][n] = grid[i / 3][j / 3][n] = true;
//                            if (dfs(board))
//                                return true;
//                            board[i][j] = '.';
//                            row[i][n] = col[j][n] = grid[i / 3][j / 3][n] = false;
//                        }
//                    }
//                    return false;
//                }
//            }
//        return true;
//    }
//};

//T26 单词搜索
//class Solution {
//    int dx[4] = { -1,1,0,0 };
//    int dy[4] = { 0,0,-1,1 };
//    bool check[7][7];
//    int m, n;
//public:
//    bool exist(vector<vector<char>>& board, string word) {
//        m = board.size();
//        n = board[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    if (dfs(board, word, i, j, 1))
//                        return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int pos)
//    {
//        if (pos == word.size())
//            return true;
//        check[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if ((x >= 0 && x < m) && (y >= 0 && y < n) && !check[x][y] && board[x][y] == word[pos])
//            {
//                if (dfs(board, word, x, y, pos + 1))
//                    return true;
//            }
//        }
//        check[i][j] = false;
//        return false;
//    }
//};


//T27 黄金矿工
//class Solution {
//    bool check[16][16];
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int ret = 0;
//    int m, n;
//public:
//    int getMaximumGold(vector<vector<int>>& grid) {
//        m = grid.size();
//        n = grid[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] != 0)
//                {
//                    dfs(grid, i, j, grid[i][j]);
//                }
//            }
//        }
//        return ret;
//    }
//    void dfs(vector<vector<int>>& grid, int i, int j, int path)
//    {
//        ret = max(path, ret);
//        check[i][j] = true;
//        int x, y;
//        for (int k = 0; k < 4; k++)
//        {
//            x = i + dx[k];
//            y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != 0 && !check[x][y])
//            {
//                dfs(grid, x, y, path + grid[x][y]);
//            }
//        }
//        check[i][j] = false;
//    }
//};

//T28 不同路径Ⅲ
//class Solution {
//    int step = 0, ret = 0;
//    bool check[20][20];
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { -1, 1, 0, 0 };
//    int m, n;
//public:
//    int uniquePathsIII(vector<vector<int>>& grid) {
//        m = grid.size();
//        n = grid[0].size();
//        int x, y;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (grid[i][j] == 0) {
//                    step++;
//                }
//                else if (grid[i][j] == 1) {
//                    x = i;
//                    y = j;
//                }
//            }
//        }
//        step++;
//        check[x][y] = true;
//        dfs(grid, x, y, 0);
//        return ret;
//    }
//
//    void dfs(vector<vector<int>>& grid, int i, int j, int count)
//    {
//        if (grid[i][j] == 2)
//        {
//            if (count == step)
//                ret++;
//            return;
//        }
//        int x, y;
//        for (int k = 0; k < 4; k++)
//        {
//            x = i + dx[k];
//            y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] != -1)
//            {
//                check[x][y] = true;
//                dfs(grid, x, y, count + 1);
//                check[x][y] = false;
//            }
//        }
//    }
//};
